GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Prediction by Partial Matching</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Prediction by Partial Matching</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><span lang="en"><b>Prediction by Partial Matching</b></span> (<b>PPM</b>, <a href="Englische_Sprache" title="Englische Sprache">englisch</a>) ist eine Familie anpassender <a href="Statistik" title="Statistik">statistischer</a> <a href="Datenkompression" title="Datenkompression">Datenkompressionsalgorithmen</a>, die auf Kontextmodellen und <a href="Prognose" title="Prognose">Prognosen</a> aufbaut. PPM-Modelle benutzen einen Satz von Symbolen aus dem vorangegangenen Symbolstrom, um das nächste Symbol des Stromes vorherzusagen.

</p><p>Voraussagen werden üblicherweise auf Wertungen der Symbole beschränkt. Die Zahl vorhergehender Symbole, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>, legt die Ordnung des PPM-Modelles fest, das als <i>PPM(n)</i> festgehalten wird. Unbegrenzte Varianten ohne Beschränkungen der Länge des Kontextes existieren auch und werden mit <i>PPM*</i> bezeichnet. Wenn aufgrund aller n Kontextsymbole keine Vorhersage gemacht werden kann, so wird eine Prognose aufgrund von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"></span> versucht. Dieses Vorgehen wird wiederholt, bis ein Treffer gefunden wird oder keine Symbole im Kontext verbleiben. Zu diesem Zeitpunkt wird eine Vorhersage festgelegt. Dieser Prozess ist die Umkehrung dessen, gefolgt von dynamischen <a href="Markow-Kette" title="Markow-Kette">Markow-Vorhersagen</a>, die von einem Modell der Ordnung 0 aufbauen.

</p><p>Ein großer Teil der Arbeit an der Optimierung eines PPM-Modells betrifft den Umgang mit Eingaben, die im Eingabestrom noch nicht auftraten. Der offensichtliche Weg damit umzugehen besteht darin, ein „Unbekannt-Symbol“ zu erzeugen, das die <a href="Escape-Sequenz" title="Escape-Sequenz">Escape-Sequenz</a> auslöst. Doch welche Wahrscheinlichkeit soll einem Symbol zugeordnet werden, das noch nie aufgetreten ist? Dies wird das <i>Problem der 0-Häufigkeit</i> genannt. Eine Vorgehensweise teilt dem „Unbekannt-Symbol“ einen festgelegten Pseudowert von 1 zu. Eine PPM-D genannte Variante erhöht den Pseudowert bei jedem Auftritt des „Unbekannt-Symbols“. (Anders ausgedrückt schätzt PPM-D also die Wahrscheinlichkeit eines neuen Symbols als das Verhältnis der Anzahl einzigartiger Symbole zur Anzahl aller Symbole insgesamt.)

</p><p>Umsetzungen von Kompression mittels PPM sind in anderen Details sehr unterschiedlich. Die eigentliche Symbolauswahl wird üblicherweise <a href="Arithmetisches_Kodieren" title="Arithmetisches Kodieren">arithmetisch kodiert</a>, obwohl auch <a href="Huffman-Kodierung" title="Huffman-Kodierung">Huffman-Kodierung</a> oder auch eine Art <a href="W%C3%B6rterbuchkompression" title="Wörterbuchkompression">Wörterbuchkodierung</a> möglich sind. Das zugrunde liegende Modell der meisten PPM-Algorithmen kann auch erweitert werden, um mehrere Symbole vorherzusagen. Es ist auch möglich, andere als die Markow-Modellerstellung zu verwenden, um diese entweder ganz zu ersetzen oder zu ergänzen. Die Symbolgröße ist für gewöhnlich statisch, typischerweise ein einzelnes Byte, was die generische Unterstützung jeglicher Dateiformate leicht macht.

</p><p>Veröffentlichungen über Forschungen an dieser Algorithmusfamilie finden sich bis zurück in die Mitte der 1980er Jahre. Softwareumsetzungen erfreuten sich bis zu den frühen 1990er Jahren keiner Beliebtheit, da PPM-Algorithmen eine beachtliche Menge an <a href="Arbeitsspeicher" title="Arbeitsspeicher">Arbeitsspeicher</a> benötigen. Neuere Umsetzungen von PPM finden sich unter den leistungsfähigsten verlustfreien Datenkompressionsverfahren für Text in <a href="Nat%C3%BCrliche_Sprache" title="Natürliche Sprache">natürlichen Sprachen</a>.

</p><p>Der Versuch, PPM-Algorithmen zu verbessern, führte zu den <a href="PAQ" title="PAQ">PAQ</a>-Kompressionsalgorithmen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>J. Cleary, I. Witten: <cite style="font-style:italic">Data Compression Using Adaptive Coding and Partial String Matching</cite>. In: <cite style="font-style:italic">Communications, IEEE Transactions on</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>32</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>4</span>, 1984, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>396–402</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1109/TCOM.1984.1096090">10.1109/TCOM.1984.1096090</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Data+Compression+Using+Adaptive+Coding+and+Partial+String+Matching&rft.au=J.+Cleary%2C+I.+Witten&rft.date=1984&rft.doi=10.1109%2FTCOM.1984.1096090&rft.genre=journal&rft.issue=4&rft.jtitle=Communications%2C+IEEE+Transactions+on&rft.pages=396-402&rft.volume=32" style="display:none"> </span></li>

<li>A. Moffat: <cite style="font-style:italic">Implementing the PPM data compression scheme</cite>. In: <cite style="font-style:italic">Communications, IEEE Transactions on</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>38</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>11</span>, 1990, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1917–1921</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1109/26.61469">10.1109/26.61469</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Implementing+the+PPM+data+compression+scheme&rft.au=A.+Moffat&rft.date=1990&rft.doi=10.1109%2F26.61469&rft.genre=journal&rft.issue=11&rft.jtitle=Communications%2C+IEEE+Transactions+on&rft.pages=1917-1921&rft.volume=38" style="display:none"> </span></li>

<li>J. G. Cleary, W. J. Teahan, I. H. Witten: <cite style="font-style:italic">Unbounded length contexts for PPM</cite>. In: <cite style="font-style:italic">Proceedings DCC-95</cite>. IEEE Computer Society Press, 1995 (<a rel="nofollow" class="external text" href="http://www.cs.waikato.ac.nz/~ihw/papers/95JC-WT-IHW-Unbound.pdf">cs.waikato.ac.nz</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Unbounded+length+contexts+for+PPM&rft.au=J.+G.+Cleary%2C+W.+J.+Teahan%2C+I.+H.+Witten&rft.btitle=Proceedings+DCC-95&rft.date=1995&rft.genre=book&rft.pub=IEEE+Computer+Society+Press" style="display:none"> </span> Alternativ: J. G. Cleary, W. J. Teahan: <cite style="font-style:italic">Unbounded Length Contexts for PPM</cite>. In: <cite style="font-style:italic">The Computer Journal</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>40</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>2–3</span>, 1997, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>67–75</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1093/comjnl%2F40.2_and_3.67">10.1093/comjnl/40.2_and_3.67</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Unbounded+Length+Contexts+for+PPM&rft.au=J.+G.+Cleary%2C+W.+J.+Teahan&rft.date=1997&rft.doi=10.1093%2Fcomjnl%2F40.2_and_3.67&rft.genre=journal&rft.issue=2-3&rft.jtitle=The+Computer+Journal&rft.pages=67-75&rft.volume=40" style="display:none"> </span></li>

<li>C. Bloom, <a rel="nofollow" class="external text" href="http://www.cbloom.com/papers/ppmz.zip">Solving the problems of context modeling</a> (<a href="ZIP-Dateiformat" title="ZIP-Dateiformat">ZIP</a>; 43 kB).</li>

<li>W. J Teahan: <cite style="font-style:italic">Probability estimation for PPM</cite>. In: <cite style="font-style:italic">Proceedings NZCSRSC'95</cite>. 1995 (<a rel="nofollow" class="external text" href="http://cotty.16x16.com/compress/peppm.htm">cotty.16x16.com</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20010605194536/http://www.cs.waikato.ac.nz/~wjt/papers/NZCSRSC.ps.gz">Original Source from archive.org</a> [abgerufen am 31. Januar 2023]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Probability+estimation+for+PPM&rft.au=W.+J+Teahan&rft.btitle=Proceedings+NZCSRSC%2795&rft.date=1995&rft.genre=book" style="display:none"> </span></li>

<li>Thomas Schürmann, <a href="Peter_Grassberger" title="Peter Grassberger">Peter Grassberger</a>: <cite style="font-style:italic">Entropy estimation of symbol sequences</cite>. In: <cite style="font-style:italic">Chaos: An Interdisciplinary Journal of Nonlinear Science</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>6</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>3</span>, 1996, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>414</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1063/1.166191">10.1063/1.166191</a></span>, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cond-mat/0203436v1">cond-mat/0203436v1</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Prediction+by+Partial+Matching&rft.atitle=Entropy+estimation+of+symbol+sequences&rft.au=Thomas+Sch%C3%BCrmann%2C+Peter+Grassberger&rft.date=1996&rft.doi=10.1063%2F1.166191&rft.genre=journal&rft.issue=3&rft.jtitle=Chaos%3A+An+Interdisciplinary+Journal+of+Nonlinear+Science&rft.pages=414&rft.volume=6" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://mattmahoney.net/dc/text.html">Paket von PPM Kompressoren mit Benchmarks</a></li>

<li><a rel="nofollow" class="external text" href="http://www3.sympatico.ca/mt0000/bicom/bicom.html">BICOM, a bijective PPM compressor</a></li>

<li><a rel="nofollow" class="external text" href="http://dogma.net/markn/articles/arith/part2.htm">"Arithmetic Coding + Statistical Modeling = Data Compression", Part 2</a></li>

<li><a rel="nofollow" class="external text" href="http://compression.ru/ds/">PPMd compressor</a> von Dmitri Shkarin</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-01-31" href="https://de.wikipedia.org/wiki/?title=Prediction_by_Partial_Matching&oldid=230401140">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>